#!/usr/bin/env python3.0
# -*- coding: utf-8 -*-

#The binomial coefficient ^(10)C_(3) = 120.
#120 = 2^(3) × 3 × 5 = 2 × 2 × 2 × 3 × 5, and 2 + 2 + 2 + 3 + 5 = 14.
#So the sum of the terms in the prime factorisation of ^(10)C_(3) is 14.
#
#Find the sum of the terms in the prime factorisation of ^(20000000)C_(15000000). 

from numth import prime_generator

def count_factor(p, n):
    result = 0
    while n > 0:
        n //= p
        result += n
    return result

def sum_factors(n):
    primes = prime_generator(max=n+1)
    result = 0
    for i in primes:
        result += i * count_factor(i, n)
    return result

n = 20000000
k = 15000000
nk = n - k

result = sum_factors(n) - (sum_factors(k) + sum_factors(nk))

print('Result: {0}'.format(result))
